package exam.xiaomi.S1;

/**
 * @Author: 18362
 * @Create: 2022-09-14 18:49:39 星期三
 */
class Solution {
    /* Write Code Here */
    public ListNode<Integer> reverseBetween(ListNode<Integer> head, int left, int right) {
        ListNode dummy = new ListNode(), p = dummy;
        dummy.next = head;
        for (int i = 0; i < left-1; i++)
            p = p.next;
        p.next = reverseK(p.next, right - left + 1);
        return dummy.next;
    }

    private ListNode<Integer> reverseK(ListNode<Integer> head, int k) {
        if (k <= 1)
            return head;
        ListNode<Integer> tHead = reverseK(head.next, k-1);
        ListNode<Integer> tail = head.next;
        head.next = tail.next;
        tail.next = head;
        return tHead;
    }
}
